Computer systems typically include diagnostic software that scans data files or received data packets to detect pattern matches indicative of problems such as computer viruses or intrusive attacks. For example, computer anti-virus software typically scans files for patterns indicative of computer viruses. Depending upon the implementation, diagnostic software may also scan data packets received from a network. For example, some types of computer intrusion software detects patterns in data packets indicative that a source of incoming data or requests is untrustworthy. As one example, intrusion detection software may look for patterns in password prompts and other information indicative of an intruder.
Conventional pattern matching software performs sequential pattern matching in which a data source is compared to different patterns in a sequence i.e., first pattern 1 is checked against the data source, then pattern 2, then pattern 3, and so on until all of the different patterns are checked. A problem with pattern matching software is that it places a substantial burden on the resources of a central processing unit (CPU). This is due in part, to the large number of patterns that must be compared in typical applications. For example, anti-virus software typically must guard against numerous different types of viruses that each require different pattern matches to be performed. As a result, many computer systems run significantly slower when anti-virus software is running in the background. Moreover, a complete anti-virus scan often takes longer than desired in many computer systems. For example, in some personal computer systems it can take several hours to perform a complete anti-virus scan of all files stored on a disk.
The demands for diagnostic pattern matching scans continues to increase. For example, anti-virus software companies regularly increase the dictionary of patterns that must be scanned in order to address new viruses or other problems, such as spyware. Additionally, diagnostic software is increasingly being applied to address new issues, such as implementing increasingly sophisticated intrusion detection algorithms. It can therefore be expected that pattern matching scanning will impose an ever increasing burden on computing resources.
Additionally, many computer systems also require data packets to be classified using software running on the CPU. Network packet classification involves the search of regions of data (such as packets from a network interface) for instances of known patterns in the data and thus also requires a form of pattern matching. There has been much research in academia and industry into efficient search algorithms; however the search operation remains both CPU and memory intensive. Packet classification can, for example, include examining the headers of data packets to classify packets based upon header fields. More generally, however, packet classification can also include a classification of data packets based upon an examination of the payload of the data packet. As computing systems evolve, there is an increasing need to classify data packets.
Therefore, in light of the problems described above the apparatus, system, and method of the present invention was developed.